#include <stdio.h>
#include <stdlib.h>

int top=-1;//top变量时刻表示栈顶元素所在位置

//二叉树节点结构
typedef struct binaryTreeNode {
    int data;   //数据域
    struct binaryTreeNode * leftChild, * rightChild;    //左右孩子指针
}binaryTreeNode_t;

//初始化树的函数
void createBinaryTree(binaryTreeNode_t * T){
    T->data = 1;
    //根节点左孩子
    T->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->leftChild->leftChild = NULL;
    T->leftChild->data = 2;
    T->leftChild->rightChild = NULL;
    //根节点右孩子
    T->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->rightChild->leftChild = NULL;
    T->rightChild->data = 3;
    T->rightChild->rightChild = NULL;
    //根节点左孩子的左孩子
    T->leftChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->leftChild->leftChild->leftChild = NULL;
    T->leftChild->leftChild->data = 4;
    T->leftChild->leftChild->rightChild = NULL;
    //根节点左孩子的右孩子
    T->leftChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->leftChild->rightChild->leftChild = NULL;
    T->leftChild->rightChild->data = 5;
    T->leftChild->rightChild->rightChild = NULL;
    //根节点右孩子的左孩子
    T->rightChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->rightChild->leftChild->leftChild = NULL;
    T->rightChild->leftChild->data = 6;
    T->rightChild->leftChild->rightChild = NULL;
    //根节点右孩子的右孩子
    T->rightChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    T->rightChild->rightChild->leftChild = NULL;
    T->rightChild->rightChild->data = 7;
    T->rightChild->rightChild->rightChild = NULL;
}

//前序遍历使用的进栈函数
void push(binaryTreeNode_t ** a, binaryTreeNode_t * elem) {
    a[++top] = elem;
}

//弹栈函数
void pop() {
    if(top == -1) {
        return;
    }
    top--;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(binaryTreeNode_t * elem) {
    printf("%d ", elem->data);
}

//拿到栈顶元素
binaryTreeNode_t * getTop(binaryTreeNode_t ** a) {
    return a[top];
}

//先序遍历非递归算法
void PreOrderTraverse(binaryTreeNode_t * T) {
    //定义一个顺序栈
    binaryTreeNode_t * a[20];
    //临时指针
    binaryTreeNode_t * p;
    //根结点进栈
    push(a, T);
    while (top != -1)
    {
        //取栈顶元素
        p=getTop(a);
        //弹栈
        pop();
        while (p)
        {
            //调用结点的操作函数
            displayElem(p);
            //如果该结点有右孩子，右孩子进栈
            if(p->rightChild) {
                push(a, p->rightChild);
            }
            //一直指向根结点最后一个左孩子
            p = p->leftChild;
        }
        
    }
    

    //如果结点为空，返回上一层
    return;
}

int main(int argc, char * argv[]) {
    binaryTreeNode_t * Tree;
    Tree = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    createBinaryTree(Tree);
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
    return 0;
}